#找出字符串中第一个匹配项的下标
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(needle)
        m = len(haystack)
        if n == 0:
            return 0
        if m < n:
            return -1
        next_array = self.get_next(needle)
        j = 0
        for i in range(m):
            while j > 0 and haystack[i] != needle[j]:
                j = next_array[j - 1]
            if haystack[i] == needle[j]:
                j += 1
            if j == n:
                return i - n + 1
        return -1

    def get_next(self, needle: str) -> list:
        n = len(needle)
        next_array = [0] * n
        j = 0
        for i in range(1, n):
            while j > 0 and needle[i] != needle[j]:
                j = next_array[j - 1]
            if needle[i] == needle[j]:
                j += 1
            next_array[i] = j
        return next_array